The present invention generally relates to a system for searching a plurality of strings necessary to classifying a protocol data unit (PDU). In particular, the invention relates to a method and apparatus for structuring the criteria of a plurality of rules in hierarchical tables and searching each table with a string extracted from the table for purposes of identifying a match and an associated pointer into the next hierarchical table.
In a packet switched network, PDUs are transmitted from node to node between the source node and destination node. At various intermediate nodes, the PDUs are inspected for purposes of making a processing decision for the PDU under inspection. In various network devices including switches and routers, for example, multiple strings, i.e. nibbles comprising one or more bits, are extracted from the PDU in order to classify the PDU. The policies used to classify the traffic may number in the thousands and such a magnitude imposes a heavy burden on the network device. The burden presents the greatest challenge to modern network devices which must maintain transfer rates in the gigabit range. There is therefore a need for a classifier that can quickly and efficiently process PDUs.